/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxFrequency1 = function (nums, k) {
  let li = []
  let obj = {}
  nums.forEach(item => {
    if (!obj[item]) {
      li.push(item)
      obj[item] = 1
    } else {
      obj[item] += 1
    }
  })
  li = li.sort((a, b) => a - b)
  let res = 0
  for (let i = li.length - 1; i >= 0; i--) {
    let tmp_k = k
    let req = obj[li[i]]
    let j = i - 1
    let hasAll = false
    while (j >= 0 && tmp_k > 0) {
      let diff = li[i] - li[j]
      if (diff <= tmp_k) {
        let c = Math.floor(tmp_k / diff)
        let tmp = Math.min(c, obj[li[j]])
        tmp_k -= diff * tmp
        hasAll = tmp === obj[li[j]]
        req += tmp
        j -= 1
        if (tmp > c) {
          break
        }
      } else {
        break
      }
    }
    res = Math.max(req, res)
    if (j === -1 && hasAll) return res
  }
  return res
}

var maxFrequency2 = function (nums, k) {
  nums = nums.sort((a, b) => a - b)
  let obj = {}
  let freq = 1
  for (let i = nums.length - 1; i > 0; i--) {
    if (nums[i + 1] && nums[i] === nums[i + 1]) {
      continue
    }
    let cur_freq = 1
    let j = i - 1
    let cur_k = k
    if (obj[i + 1]) {
      let [prev_idx, prev_k] = obj[i + 1]
      if (j < prev_idx) {
        cur_freq = i - prev_idx
        j = prev_idx
        cur_k = prev_k - (nums[i] - nums[i - 1]) * (i - prev_idx)
      }
    }
    let use_k = cur_k
    while (j >= 0 && cur_k > 0) {
      let diff = nums[i] - nums[j]
      if (diff <= cur_k) {
        cur_k -= diff
        use_k += diff
        cur_freq += 1
        j--
        obj[i] = [j, use_k]
      } else {
        break
      }
    }
    freq = Math.max(freq, cur_freq)
    if (j === -1) {
      return freq
    }
  }
  return freq
}
var maxFrequency = function (nums, k) {
  nums.sort((a, b) => a - b)
  let tmpSum = 0
  let max = 0
  for (let r = nums.length - 1, l = nums.length - 1; r >= 0; r--) {
    while (nums[r] * (r - l) - tmpSum <= k) {
      max = Math.max(r - l, max)
      tmpSum += nums[l--]
    }
    tmpSum -= nums[r]
  }
  return max
}
// 从左往右遍历
var maxFrequency3 = function (nums, k) {
  nums.sort((a, b) => a - b)
  let max = 0
  let tempSum = 0
  for (let l = 0, r = 0; r < nums.length; r++) {
    while (nums[r] * (r - l) - tempSum > k) {
      tempSum -= nums[l++]
    }
    tempSum += nums[r]
    max = Math.max(max, r - l + 1)
  }
  return max
}

let nums = [3, 9, 6]
let k = 2
// nums = [1, 2, 4]
// k = 5
// nums = [1, 1, 1, 1, 1, 1, 1, 1, 1, 10]
// k = 10
// nums = [
//   9940, 9995, 9944, 9937, 9941, 9952, 9907, 9952, 9987, 9964, 9940, 9914, 9941,
//   9933, 9912, 9934, 9980, 9907, 9980, 9944, 9910, 9997
// ]
// k = 7925
let res = maxFrequency(nums, k)
console.log('res: ', res)
res = maxFrequency3(nums, k)
console.log('res: ', res)
